COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	This is called search on [let,rwf]
C00005 ENDMK
C⊗;
This is called search on [let,rwf]

Many computer algorithms that solve problems of economic importance require
prohibitively long computations.  For some of these problems, there are
alternate approximate methods of solution that are fast and come close to the
best solutions.  The traveling salesman problem (routing service calls)
is an example.  Many of the quick aproximations are ``greedy'' algorithms:
they choose actions based on sort-term cost-effectiveness.

An optimal search strategy for a table, such as a dictionary, index, directory,
or catalog, can readily be constructed, but the required time is proportionate
to the cube of the table size.  A greedy search that always inspects the
table entry that gives maximum information (by Shannon's quantitative
measure) can be designed quickly.  During the winter and spring of 1988,
Alan Hu and I examined whether the performance of greedy search approximates
that of optimal search.

We found that greedy search may be slower than optimal search by arbitrarily large
amounts.  In fact, we learned to construct search problems for which the
difference is as great as you please.  This disappointing result provides a
useful caution to programmers of searching techniques, and uses methods that may
prove useful in performance evaluation of other greedy algorithms.

I defined the problem and suggested how to look for tables on which the greedy
algorithm might perform poorly.  Hu explored a series of possibilities
empirically with the aid of a computer, discovering patterns that we
elaborated to get arbitrarily poor performance.  Hu is a full partner in this
investigation, and will be a coauthor in resulting publication.
\bye